package com.tys.algorithm.bak.code2;

import java.util.Arrays;

//计数排序：数组arr存储是员工年龄，从小到大排序
public class Code36_CountSort {
    //处理0-200的值
    // only for 0~200 value
    public static void countSort(int[] arr) {
        //判断边界
        if (arr == null || arr.length < 2) {
            return;
        }
        //数组最大值，初始赋值设置为整数最小值
        int max = Integer.MIN_VALUE;
        //遍历数组找到数组中的最大值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        //根据数组最大值max新建一个整数数组桶
        int[] bucket = new int[max + 1];
        //遍历数组：用arr的值作为桶bucket的索引，每加一个桶位置加1
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }

        int i = 0;
        //遍历桶
        for (int j = 0; j < bucket.length; j++) {
            //根据桶位置计数重新填充arr完成排序
            //根据桶的中对应值 = arr中对应数据的个数
            while (bucket[j]-- > 0) {
                //将排序后的数重新赋值给arr
                arr[i++] = j; //桶索引 = arr中的值
            }
        }
    }

    //调用系统比较
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    //生成随机数组
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    //拷贝数组
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    //比较两个数组是否相等
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    //打印数组
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    //测试
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 150;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            countSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
//        int[] arr = generateRandomArray(maxSize, maxValue);
//        printArray(arr);
//        countSort(arr);
//        printArray(arr);
    }
}
